package leecode.mid;


import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: xieZW
 * @Date: 2022/3/1 14:03
 * 不同的二查搜索树
 * 输入：n = 3
 * 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
 */
public class Index95 {

    @Test
    public void fun() {
        List<TreeNode> treeNodes = generateTrees(3);
        System.out.println("treeNodes = " + treeNodes);
    }

    public List<TreeNode> generateTrees(int n) {
        //每个值都可以当根,该值左边的在左子树,该值右边的在右子树
        //用到递归
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        List<TreeNode> treeList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            Set<Integer> set = new HashSet<>();
            Integer val = list.get(i);
            if (set.add(val)) {
                TreeNode treeNode = new TreeNode(val);
                if (i - 1 >= 0) {
                    treeNode.left = generateTree(list, i - 1, set);
                }
                if (i + 1 <= list.size() - 1) {
                    treeNode.right = generateTree(list, i + 1, set);
                }
                treeList.add(treeNode);
            }
        }

        return treeList;
    }

    //123
    private TreeNode generateTree(List<Integer> list, Integer i, Set set) {

        Integer val = list.get(i);
        if (set.add(val)) {
            TreeNode treeNode = new TreeNode(val);
            if (i - 1 >= 0) {
                treeNode.left = generateTree(list, i - 1, set);
            }
            if (i + 1 <= list.size() - 1) {
                treeNode.right = generateTree(list, i + 1, set);
            }
            return treeNode;
        }
        return null;
    }
}
